/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/next-greater-element-ii
   @Language: C++
   @Datetime: 19-05-16 16:10
   */

class Solution {
public:
	/**
	 * @param nums: an array
	 * @return: the Next Greater Number for every element
	 */
	vector<int> nextGreaterElements(vector<int> &nums) {
		// Write your code here
		int n=nums.size();
		stack<pair<int,int> > s;    // num, index
		vector<int> v(n,-1);
		for(int i=0; i<n*2; ++i){
			for(; s.size() && s.top().first<nums[i%n]; s.pop())
				v[s.top().second]=nums[i%n];
			s.push(make_pair(nums[i%n], i%n));
		}
		return v;
	}
};
